package com.atguigui.leetcode1;

import java.util.Arrays;

/**
 * 1626.无矛盾的最佳球队
 * Project: leetcode
 * Package: com.atguigui.leetcode1
 * Version: 1.0
 * <p>
 * Created by WJX on 2023/3/22 9:39
 */
public class P1626BestTeamWithNoConflicts {
    public static void main(String[] args) {
        Solution solution = new P1626BestTeamWithNoConflicts().new Solution();
        // TO TEST
    }

    class Solution {
        public int bestTeamScore(int[] scores, int[] ages) {

            int n = scores.length;
            int[][] people = new int[n][2];
            for (int i = 0; i < n; ++i) {
                people[i] = new int[]{scores[i], ages[i]};
            }
            //按照得分进行排序，得分相同按照年龄排序
            Arrays.sort(people, (a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);

            int[] dp = new int[n];
            int res = 0;
            //计算所有可能性
            for (int i = 0; i < n; ++i) {
                for (int j = i - 1; j >= 0; --j) {
                    if (people[j][1] <= people[i][1]) {
                        dp[i] = Math.max(dp[i], dp[j]);
                    }
                }
                dp[i] += people[i][0];
                res = Math.max(res, dp[i]);
            }

            return res;
        }
    }
}
